class AbstractIntVector
{
public:
    virtual ~AbstractIntVector() {}
    virtual void clear() = 0;
    virtual void increment(int i) = 0;
    virtual double dot(const vector<double> &other) const = 0;
    virtual const vector<int> & indices() const  = 0;
};

class SparseIntVector : public AbstractIntVector
{
public:
    void clear();
    void increment(int i);
    double dot(const vector<double> &other) const;
    const vector<int> & indices() const { return _indices;}

private:
    vector<int> _indices;
};

class DenseIntVector : public AbstractIntVector
{
public:
    DenseIntVector(UINT size) : _size(size), _data(size) {}
    void clear() { _data.clear(); _data.resize(_size); }
    void increment(int i) { _data[i]++; }
    double dot(const vector<double> &other) const
    {
        double sum = 0;
        for (UINT i = 0; i < _size; i++) sum += _data[i] * other[i];
        return sum;
    }
    virtual const vector<int> & indices() const
    {
        _indices.clear();
        for (UINT i = 0; i < _data.size(); i++) {
            if (_data[i] != 0) _indices.insert(_indices.end(), _data[i], i);
        }
        return _indices;
    }
private:
    UINT _size;
    vector<int> _data;
    mutable vector<int> _indices;
};